{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #乐团站位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: orchestraLayout"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #乐团站位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "某乐团的演出场地可视作 `num * num` 的二维矩阵 `grid`（左上角坐标为 `[0,0]`)，每个位置站有一位成员。乐团共有 `9` 种乐器，乐器编号为 `1~9`，每位成员持有 `1` 个乐器。\n",
    "\n",
    "为保证声乐混合效果，成员站位规则为：自 `grid` 左上角开始顺时针螺旋形向内循环以 `1，2，...，9` 循环重复排列。例如当 num = `5` 时，站位如图所示\n",
    "\n",
    "![image.png](https://pic.leetcode-cn.com/1616125411-WOblWH-image.png)\n",
    "\n",
    "\n",
    "请返回位于场地坐标 [`Xpos`,`Ypos`] 的成员所持乐器编号。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`num = 3, Xpos = 0, Ypos = 2`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：\n",
    "![image.png](https://pic.leetcode-cn.com/1616125437-WUOwsu-image.png)\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`num = 4, Xpos = 1, Ypos = 2`\n",
    ">\n",
    ">输出：`5`\n",
    ">\n",
    ">解释：\n",
    "![image.png](https://pic.leetcode-cn.com/1616125453-IIDpxg-image.png)\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= num <= 10^9`\n",
    "- `0 <= Xpos, Ypos < num`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [SNJvJP](https://leetcode.cn/problems/SNJvJP/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [SNJvJP](https://leetcode.cn/problems/SNJvJP/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n0\\n2', '4\\n1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "\n",
    "        '''找规律，数学题'''\n",
    "        # 为了写的方便\n",
    "        x, y = xPos, yPos\n",
    "        # 计算处在第几层\n",
    "        m = min(x, y, num - x - 1, num - y - 1)\n",
    "        # 计算前m-1层一共有多少个数字,总结一下规律就是一个等差数列\n",
    "        total = 4 * m * (num-m)\n",
    "        # 判断出第m层第一个数字是什么\n",
    "        m_first = 9 if (total+1) % 9 == 0 else (total + 1) % 9 \n",
    "        # 计算出第m层有多少个数字\n",
    "        m_num = 4 * (num-1-2*m)\n",
    "        # 判断当前的数字位于第m层的第几个\n",
    "        \n",
    "        # 分两种情况，一种是y的坐标大于等于x的坐标，一种是y的坐标小于x的坐标\n",
    "        # 如果是第一种情况，直接正着数若干个，如果是第二种情况，倒着数若干个\n",
    "        # 接下来说一下怎么求这个若干个，举个简单例子，\n",
    "        \"\"\"\n",
    "            如果我们就位于第一层，按照索引说是第0层，那么顺时针的时候观察索引的变化，\n",
    "            是不是用横坐标加纵坐标加1就是第几个数，其实是减去了层数，也就是 x - 0 + y - 0 + 1\n",
    "            那么如果是在第m层不就是 x - m + y - m + 1\n",
    "\n",
    "            当然如果是第二种情况这时候正着的计算方法就不对了，我们可以使用这一层的数字总数减去 x - m + y - m 加 1\n",
    "            因为如果2 - 1 等于1, 2 其实是位于第二个数\n",
    "        \"\"\"\n",
    "        # 接着看代码\n",
    "        if x <= y: # 正着数\n",
    "            count = x - m + y - m + 1\n",
    "        else: # 倒着数\n",
    "            count = m_num - (x - m + y - m) + 1\n",
    "        \n",
    "        # 得到了第一个数，得到了第几个，接下来简单多了吧\n",
    "        res = 9 if (m_first + count - 1) % 9 == 0 else (m_first + count - 1) % 9\n",
    "\n",
    "        return res\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        xPos, yPos = yPos, xPos\n",
    "        k = min([xPos, num - xPos - 1, yPos, num - yPos - 1])\n",
    "        path_len = (4 * num - 4 * k) * k\n",
    "        if yPos == k:\n",
    "            path_len += xPos - k + 1\n",
    "        elif xPos == num - k - 1:\n",
    "            path_len += num - 2 * k + (yPos - k)\n",
    "        elif yPos == num - k - 1:\n",
    "            path_len += 3 * num - 5 * k - 2 - xPos\n",
    "        else:\n",
    "            path_len += 4 * num - 7 * k - 3 - yPos\n",
    "        return path_len % 9 if path_len % 9 != 0 else 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        layer = min(num - 1 - xPos, num - 1 - yPos, xPos, yPos)\n",
    "        res = 4 * ((num - 1 + num - 1 - 2 * (layer - 1)) * layer // 2) + (xPos - layer + yPos - layer if yPos >= xPos else 4 * (num - 1 - 2 * layer) - (xPos - layer + yPos - layer))\n",
    "        return res % 9 + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        \n",
    "        key = min(xPos, yPos, num-1-xPos, num-1-yPos)   ###最外圈，可以直接去掉\n",
    "        ################## (xPos, yPos)一定在内部正方形的边上\n",
    "        up = key            #上\n",
    "        down = num-1-key    #下\n",
    "        left = key          #左\n",
    "        right = num-1-key   #右\n",
    "        \n",
    "        ID = num**2 - (num-2*key)**2       #大正方形点的个数 - 内部正方形点的个数\n",
    "        ID %= 9\n",
    "        res = 0\n",
    "        ################ (xPos, yPos)一定在内部正方形的边上了 顺时针挨着走\n",
    "\n",
    "        ######情况1\n",
    "        if up == xPos:      #如果上，是行号\n",
    "            res = (ID + yPos - left + 1) % 9\n",
    "            return res if res!=0 else 9\n",
    "        else:\n",
    "            ID += (right - left + 1)   #右-左+1 （步长）\n",
    "\n",
    "        up += 1         #下移一行\n",
    "        ######情况2\n",
    "        if right == yPos:   #如果右是列号\n",
    "            res = (ID + xPos - up + 1) % 9\n",
    "            return res if res!=0 else 9\n",
    "        else:\n",
    "            ID += (down - up + 1)      #下-上+1 （步长）\n",
    "        \n",
    "        right -= 1      #左移一列\n",
    "        ######情况3 \n",
    "        if down == xPos:    #如果在底边上\n",
    "            res = (ID + right - yPos + 1) % 9\n",
    "            return res if res!=0 else 9\n",
    "        else:\n",
    "            ID += (right - left + 1)   #左-右+1 （步长）\n",
    "        \n",
    "        down -= 1   #上移一行\n",
    "        ######情况4\n",
    "        if left == yPos:\n",
    "            res = (ID + down - xPos + 1) % 9\n",
    "            return res if res else 9\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        layer = min([xPos, num - xPos - 1, yPos, num - yPos - 1])  # 位于第几圈\n",
    "        v = (num * layer * 4 - layer * layer * 4) % 9  # 前几圈有多少个元素\n",
    "\n",
    "        start, end = layer, num - layer - 1\n",
    "\n",
    "        if xPos == start:\n",
    "            return (v + yPos - start) % 9 + 1\n",
    "\n",
    "        if yPos == end:\n",
    "            return (v + (end - start + 1) * 1 - 1 + xPos - start) % 9 + 1\n",
    "\n",
    "        if xPos == end:\n",
    "            return (v + (end - start + 1) * 2 - 2 + end - yPos) % 9 + 1\n",
    "\n",
    "        if yPos == start:\n",
    "            return (v + (end - start + 1) * 3 - 3 + end - xPos) % 9 + 1\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        left=yPos\n",
    "        right=num-1-yPos\n",
    "        up=xPos\n",
    "        down=num-1-xPos\n",
    "        n=min(left,right,up,down)\n",
    "        r=(num-n)*4*n\n",
    "        xP=xPos-n\n",
    "        yP=yPos-n\n",
    "        n_new=num-2*n\n",
    "        if xP==0:\n",
    "            r+=yP+1\n",
    "        elif yP==n_new-1:\n",
    "            r+=n_new+xP\n",
    "        elif xP==n_new-1:\n",
    "            r+=(3*(n_new-1)-yP+1)\n",
    "        elif yP==0:\n",
    "            r+=(4*(n_new-1)-xP+1)\n",
    "        x=r%9\n",
    "        return 9 if x==0 else x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 象限计数法\n",
    "    '''LCP 29:某乐团的演出场地可视作 num * num 的二维矩阵 grid（左上角坐标为 [0,0])，\n",
    "    每个位置站有一位成员。乐团共有 9 种乐器，乐器编号为 1~9，每位成员持有 1 个乐器。\n",
    "    为保证声乐混合效果，成员站位规则为：自 grid 左上角开始顺时针螺旋形向内循环以 \n",
    "    1，2，...，9 循环重复排列。例如当 num = 5 时，站位如图所示'''\n",
    "    def quadrant(self, num:int, xp:int, yp:int) -> int:\n",
    "        leftd_right = True if yp >= xp else False\n",
    "        rightd_right = True if xp + yp >= (num - 1) else False\n",
    "        if leftd_right and not rightd_right:\n",
    "            return 0\n",
    "        elif leftd_right and rightd_right:\n",
    "            return 1\n",
    "        elif not leftd_right and rightd_right:\n",
    "            return 2\n",
    "        else:\n",
    "            return 3\n",
    "    \n",
    "    def sum_beyond_loop(self, num:int, n:int) -> int:\n",
    "        top = num - 1\n",
    "        bot = num - (1 + 2 * (n - 1))\n",
    "        hi = n\n",
    "        return ((top + bot) * hi // 2) * 4\n",
    "        # sum_ = 0\n",
    "        # for i in range(n):\n",
    "        #     quart_unit = num - (1 + 2 * i)\n",
    "        #     sum_ += 4 * quart_unit\n",
    "        # return sum_\n",
    "\n",
    "    def countpos(self, num:int, xp:int, yp: int) -> int:\n",
    "        \n",
    "        quad = self.quadrant(num, xp, yp)\n",
    "        if quad == 0:\n",
    "            loopn = xp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数\n",
    "            unit_range =  yp - xp + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 1:\n",
    "            loopn = num - 1 - yp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  xp + yp - (num - 1) + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 2:\n",
    "            loopn = num - 1 - xp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  xp - yp + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 3:\n",
    "            loopn = yp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  (num - 1) - (xp + yp) + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        else:\n",
    "            raise ValueError\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        tem = self.countpos(num, xPos, yPos)\n",
    "        return (tem - 1) % 9 + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        #完整地走过了几个正方形\n",
    "        #1.如果位于上面边\n",
    "        n = num\n",
    "        x, y = xPos, yPos\n",
    "        if y >= x and y + x < n - 1:\n",
    "            st = (x, x)\n",
    "            full = x\n",
    "            steps = y - x + 1\n",
    "            \n",
    "        #2.如果位于右边    \n",
    "        elif x + y >= n - 1 and x < y:\n",
    "            st = (n-1-y ,y)\n",
    "            #print(st)\n",
    "            full = n - 1 - y\n",
    "            #print(full)\n",
    "            steps = x - (n - 1 - y) + 1 \n",
    "            steps += 1 * (n - 2 * full - 1) \n",
    "        #3.如果位于下边\n",
    "        elif x >= y and x + y > n - 1:\n",
    "            st = (x, x)\n",
    "            full = n - 1 - x\n",
    "            steps = x - y + 1\n",
    "            steps += 2 * (n - 2 * full - 1)\n",
    "        #4.如果位于左边    \n",
    "        else:\n",
    "            st = (n - 1 - y ,y)\n",
    "            full = y\n",
    "            steps = n - 1 - y - x + 1\n",
    "            steps += 3 * (n - 2 * full - 1)\n",
    "\n",
    "\n",
    "        full_step = 4 * full * n - 4 * full * full\n",
    "        steps += full_step\n",
    "\n",
    "        if steps % 9 == 0:\n",
    "            return 9\n",
    "        return steps % 9\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        l = 0\n",
    "        r = num-1\n",
    "        u = 0\n",
    "        d = num -1\n",
    "        k = 0\n",
    "        a = min(xPos, r-xPos, yPos, d-yPos)\n",
    "        k += 4*(num-a)*a\n",
    "        num -= 2*a\n",
    "        xPos-=a\n",
    "        yPos-=a\n",
    "        l = 0\n",
    "        r = num-1\n",
    "        u = 0\n",
    "        d = num -1\n",
    "\n",
    "        if(xPos == 0):\n",
    "            k += yPos+1\n",
    "        elif(yPos == r):\n",
    "            k += num+xPos\n",
    "        elif(xPos == d):\n",
    "            k += 2*num-1+(r-yPos)\n",
    "        elif(yPos == 0):\n",
    "            k += 3*num-2+(d-xPos)\n",
    "        else:\n",
    "            pass\n",
    "        ans = k%9 if k%9!=0 else 9\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, n: int, x: int, y: int) -> int:\n",
    "        x += 1\n",
    "        y += 1\n",
    "        layer = min(x - 1, n - x, y - 1, n - y)\n",
    "        s = 4 * (n - layer) * layer\n",
    "        s = s % 9\n",
    "        if x == layer + 1:\n",
    "            extra = y - layer - 1\n",
    "            return (extra + s) % 9 + 1\n",
    "        s = (s + n - 2 * layer - 1) % 9\n",
    "        if y == n - layer:\n",
    "            extra = x - layer - 1\n",
    "            return (extra + s) % 9 + 1\n",
    "        s = (s + n - 2 * layer - 1) % 9\n",
    "        if x == n - layer:\n",
    "            extra = n - layer - y\n",
    "            return (extra + s) % 9 + 1\n",
    "        s = (s + n - 2 * layer - 1) % 9\n",
    "        if y == layer + 1:\n",
    "            extra = n - layer - x\n",
    "            return (extra + s) % 9 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        # (5+1)//2 圈 第一圈 1 开始, num=971131546 TLE\n",
    "        # 第二圈4*(num-1)%9+1\n",
    "        # 第三圈4*(num-2-1)%9+1\n",
    "        n0=range(1,10)\n",
    "        loops=[1]\n",
    "        loopsum=0\n",
    "        testnum=num\n",
    "        # while testnum>1:\n",
    "        #     # print(4*(testnum-1))\n",
    "        #     loopsum+=4*(testnum-1)\n",
    "        #     loops.append((loopsum)%9+1)\n",
    "        #     testnum-=2\n",
    "        # print(loops) 四条边:(0,i)(j,m)(m,j)(i,0)\n",
    "        ldx0=min(xPos,num-1-xPos,yPos,num-1-yPos)\n",
    "        l4 = (num-2*ldx0)\n",
    "        # a**2-b**2=(a+b)*(a-b)\n",
    "        loops[0]=(num+l4)*(num-l4)%9+1\n",
    "        # print(loops[ldx])\n",
    "        dx,dy = (xPos-ldx0,yPos-ldx0)\n",
    "        if dx==0: # n0=[1.2.3.....9]\n",
    "            return ((loops[0]-1)+dy)%9 + 1\n",
    "        elif dy==l4-1:\n",
    "            return ((loops[0]-1)+dy+dx)%9 + 1\n",
    "        elif dx==l4-1:\n",
    "            return ((loops[0]-1)+2*dx+dx-dy)%9 + 1\n",
    "        else:\n",
    "            return ((loops[0]-1)+3*(l4-1)+(l4-1)-dx)%9 + 1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        def start(num,x,y,start_num):\n",
    "            if(num==1):\n",
    "                return start_num\n",
    "            elif(num==2):\n",
    "                if(x==0 and y==0):\n",
    "                    v=0\n",
    "                elif(x==0 and y==1):\n",
    "                    v=1\n",
    "                elif(x==1 and y==1):\n",
    "                    v=2\n",
    "                else:\n",
    "                    v=3\n",
    "                return (start_num+v)%9\n",
    "            elif(x==0):\n",
    "                return (start_num+y)%9\n",
    "            elif(x==num-1):\n",
    "                return (start_num+3*num-3-y)%9\n",
    "            elif(y==0):\n",
    "                return (start_num+4*num-4-x)%9\n",
    "            elif(y==num-1):\n",
    "                return (start_num+num+x-1)%9\n",
    "            else:\n",
    "                return start(num-2,x-1,y-1,(start_num+4*num-4)%9)\n",
    "        tens=min(xPos//9,yPos//9,(num-xPos-1)//9,(num-yPos-1)//9)\n",
    "        # print(tens)\n",
    "        # print(num-tens*6,xPos-tens*3,yPos-tens*3)\n",
    "        return start(num-tens*18,xPos-tens*9,yPos-tens*9,0)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        #完整地走过了几个正方形\n",
    "        #1.如果位于上面边\n",
    "        n = num\n",
    "        x, y = xPos, yPos\n",
    "        if y >= x and y + x < n - 1:\n",
    "            st = (x, x)\n",
    "            full = x\n",
    "            steps = y - x + 1\n",
    "            \n",
    "        #2.如果位于右边    \n",
    "        elif x + y >= n - 1 and x < y:\n",
    "            st = (n-1-y ,y)\n",
    "            full = n - 1 - y\n",
    "            steps = x - (n - 1 - y) + 1 \n",
    "            steps += 1 * (n - 2 * full - 1) \n",
    "        #3.如果位于下边\n",
    "        elif x >= y and x + y > n - 1:\n",
    "            st = (x, x)\n",
    "            full = n - 1 - x\n",
    "            steps = x - y + 1\n",
    "            steps += 2 * (n - 2 * full - 1)\n",
    "        #4.如果位于左边    \n",
    "        else:\n",
    "            st = (n - 1 - y ,y)\n",
    "            full = y\n",
    "            steps = n - 1 - y - x + 1\n",
    "            steps += 3 * (n - 2 * full - 1)\n",
    "\n",
    "\n",
    "        full_step = 4 * full * n - 4 * full * full\n",
    "        steps += full_step\n",
    "\n",
    "        if steps % 9 == 0:\n",
    "            return 9\n",
    "        return steps % 9\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 象限计数法\n",
    "    '''LCP 29:某乐团的演出场地可视作 num * num 的二维矩阵 grid（左上角坐标为 [0,0])，\n",
    "    每个位置站有一位成员。乐团共有 9 种乐器，乐器编号为 1~9，每位成员持有 1 个乐器。\n",
    "    为保证声乐混合效果，成员站位规则为：自 grid 左上角开始顺时针螺旋形向内循环以 \n",
    "    1，2，...，9 循环重复排列。例如当 num = 5 时，站位如图所示'''\n",
    "    def quadrant(self, num:int, xp:int, yp:int) -> int:\n",
    "        leftd_right = True if yp >= xp else False\n",
    "        rightd_right = True if xp + yp >= (num - 1) else False\n",
    "        if leftd_right and not rightd_right:\n",
    "            return 0\n",
    "        elif leftd_right and rightd_right:\n",
    "            return 1\n",
    "        elif not leftd_right and rightd_right:\n",
    "            return 2\n",
    "        else:\n",
    "            return 3\n",
    "    \n",
    "    def sum_beyond_loop(self, num:int, n:int) -> int:\n",
    "        top = num - 1\n",
    "        bot = num - (1 + 2 * (n - 1))\n",
    "        hi = n\n",
    "        return ((top + bot) * hi // 2) * 4\n",
    "        # sum_ = 0\n",
    "        # for i in range(n):\n",
    "        #     quart_unit = num - (1 + 2 * i)\n",
    "        #     sum_ += 4 * quart_unit\n",
    "        # return sum_\n",
    "\n",
    "    def countpos(self, num:int, xp:int, yp: int) -> int:\n",
    "        \n",
    "        quad = self.quadrant(num, xp, yp)\n",
    "        if quad == 0:\n",
    "            loopn = xp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数\n",
    "            unit_range =  yp - xp + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 1:\n",
    "            loopn = num - 1 - yp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  xp + yp - (num - 1) + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 2:\n",
    "            loopn = num - 1 - xp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  xp - yp + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 3:\n",
    "            loopn = yp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  (num - 1) - (xp + yp) + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        else:\n",
    "            raise ValueError\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        tem = self.countpos(num, xPos, yPos)\n",
    "        return (tem - 1) % 9 + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 象限计数法\n",
    "    '''LCP 29:某乐团的演出场地可视作 num * num 的二维矩阵 grid（左上角坐标为 [0,0])，\n",
    "    每个位置站有一位成员。乐团共有 9 种乐器，乐器编号为 1~9，每位成员持有 1 个乐器。\n",
    "    为保证声乐混合效果，成员站位规则为：自 grid 左上角开始顺时针螺旋形向内循环以 \n",
    "    1，2，...，9 循环重复排列。例如当 num = 5 时，站位如图所示'''\n",
    "    def quadrant(self, num:int, xp:int, yp:int) -> int:\n",
    "        leftd_right = True if yp >= xp else False\n",
    "        rightd_right = True if xp + yp >= (num - 1) else False\n",
    "        if leftd_right and not rightd_right:\n",
    "            return 0\n",
    "        elif leftd_right and rightd_right:\n",
    "            return 1\n",
    "        elif not leftd_right and rightd_right:\n",
    "            return 2\n",
    "        else:\n",
    "            return 3\n",
    "    \n",
    "    def sum_beyond_loop(self, num:int, n:int) -> int:\n",
    "        top = num - 1\n",
    "        bot = num - (1 + 2 * (n - 1))\n",
    "        hi = n\n",
    "        return ((top + bot) * hi // 2) * 4\n",
    "        # sum_ = 0\n",
    "        # for i in range(n):\n",
    "        #     quart_unit = num - (1 + 2 * i)\n",
    "        #     sum_ += 4 * quart_unit\n",
    "        # return sum_\n",
    "\n",
    "    def countpos(self, num:int, xp:int, yp: int) -> int:\n",
    "        \n",
    "        quad = self.quadrant(num, xp, yp)\n",
    "        if quad == 0:\n",
    "            loopn = xp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数\n",
    "            unit_range =  yp - xp + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 1:\n",
    "            loopn = num - 1 - yp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  xp + yp - (num - 1) + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 2:\n",
    "            loopn = num - 1 - xp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  xp - yp + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        elif quad == 3:\n",
    "            loopn = yp\n",
    "            # 下面计算，在本循环中排第几个，从1开始排\n",
    "            delta = num - (1 + 2 * loopn) # 本循环，1/4包含个数，固定\n",
    "            unit_range =  (num - 1) - (xp + yp) + 1 # 此象限排第几个，1开始\n",
    "            local_range = quad * delta + unit_range # 本循环排第几个，1开始，固定\n",
    "            return self.sum_beyond_loop(num, loopn) + local_range\n",
    "        else:\n",
    "            raise ValueError\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        tem = self.countpos(num, xPos, yPos)\n",
    "        return (tem - 1) % 9 + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        i=0\n",
    "        if xPos!=0 and xPos!=num-1 and yPos!=0 and yPos!=num-1:\n",
    "            a=min(xPos-0,yPos-0,num-xPos-1,num-yPos-1)\n",
    "            i=num**2-(num-2*a)**2\n",
    "            num-=a*2\n",
    "            xPos-=a\n",
    "            yPos-=a\n",
    "\n",
    "        if xPos==0:\n",
    "             if (i+yPos+1)%9==0:\n",
    "                return 9\n",
    "             else:\n",
    "                return (i+yPos+1)%9\n",
    "        elif xPos==num-1:\n",
    "            if (i+(num-1)*2+(num-yPos))%9 == 0:\n",
    "                return 9\n",
    "            else:\n",
    "                return (i+(num-1)*2+(num-yPos))%9\n",
    "\n",
    "        elif yPos==0:\n",
    "            if (i+(num-1)*3+(num-xPos))%9 == 0:\n",
    "                return 9\n",
    "            else:\n",
    "                return (i+(num-1)*3+(num-xPos))%9\n",
    "\n",
    "        elif yPos==num-1:\n",
    "            if (i+(num-1)+xPos+1)%9 == 0:\n",
    "                return 9\n",
    "            else:\n",
    "                return (i+(num-1)+xPos+1)%9\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        mid = num //2\n",
    "        if xPos >= mid:\n",
    "            x = num - 1 - xPos\n",
    "        else:\n",
    "            x = xPos\n",
    "        if yPos >= mid:\n",
    "            y = num - 1 - yPos\n",
    "        else:\n",
    "            y = yPos\n",
    "        c = min(x, y)\n",
    "        idx = 0\n",
    "        idx = (num-c)*4*c\n",
    "        xPos -= c\n",
    "        yPos -= c\n",
    "        num -= c*2\n",
    "        if xPos == 0:\n",
    "            idx += yPos\n",
    "        elif xPos == num - 1:\n",
    "            idx += num * 3 - yPos - 3\n",
    "        elif yPos == num - 1:\n",
    "            idx += num + xPos - 1\n",
    "        else:\n",
    "            idx += num * 4 - xPos - 4\n",
    "        return idx % 9 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, N: int, x: int, y: int) -> int:\n",
    "        L = min(x, N - 1 - x, y, N - 1 - y)\n",
    "        ans = 4 * (N - L) * L\n",
    "        #print(L, ans)\n",
    "        x -= L\n",
    "        y -= L\n",
    "        N -= 2 * L\n",
    "        #print(L, x, y, N)\n",
    "        if x == 0:\n",
    "            ans += y + 1\n",
    "        elif y == N - 1:\n",
    "            ans += N\n",
    "            ans += x\n",
    "        elif x == N - 1:\n",
    "            ans += N + N - 1\n",
    "            ans += N - 1 - y\n",
    "        else:\n",
    "            ans += N + N - 1 + N - 1\n",
    "            ans += N - 1 - x\n",
    "        return (ans - 1) % 9 + 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def orchestraLayout(self, num: int, xPos: int, yPos: int) -> int:\n",
    "        layer = min(num - 1 - xPos, num - 1 - yPos, xPos, yPos)\n",
    "        f1 = 4 * ((num - 1 + num - 1 - 2 * (layer - 1)) * layer // 2) \n",
    "        \n",
    "        if yPos >= xPos:\n",
    "            f = xPos - layer + yPos - layer\n",
    "        else:\n",
    "            f = 4 * (num - 1 - 2 * layer) - (xPos - layer + yPos - layer)\n",
    "        res = f1 + f\n",
    "        #res = 4 * ((num - 1 + num - 1 - 2 * (layer - 1)) * layer // 2) + (xPos - layer + yPos - layer if yPos >= xPos else 4 * (num - 1 - 2 * layer) - (xPos - layer + yPos - layer))\n",
    "        return res % 9 + 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
